Introduction to Highway Hierarchy

Tony Li

Background

• In the real world, we always consider the

following route planning method:

1 Look for a reasonable motorway

2 Drive on motorways to a location close to

the target

3 Drive to the target from the motorway exit

• It may be not optimal, but we usually do not

leave the motorway to drive on a faster way

in the city.

Hierarchy

Local

• Local Area (also called Neighborhood, N(s))

nodes(and related edges) around a node s

• Size of N(s):

All nodes are settled in a fixed

order during a Dijkstra search from s.

The first H settled nodes

(and related edges) belong to

N(s), i.e., |N(s)|=H

• Radius:= max{dist(s,t)|t in N(s)}

 N(s):={v|dist(s,v)<=Radius}

Highway

• Highway

Nodes and Edges not in the Local Area

Bypassed Node

• There are paths consisting of degree-2

nodes. Such nodes could be bypassed by

introducing shortcut edges.

• Simplify the network and save the query

time

Core

• The sub-graph induced by the set of non-

bypassed nodes (also called core nodes)

and additional shortcut edges

Highway Hierarchy

• Step 1 Organize the topology info of a road

network into a well designed multi-level

architecture --- Preprocessing

• Step 2 Query the route from source to target

with very high efficiency --- Query

Preprocessing

Determine N(s) for each s

Partial Shortest Path

Tree Construction

Highway Edge

Selection

Highway Network

Contraction

For each s:

Add Highway Edge to Highway

Network of Next Level

Contraction

• Bypass the nodes iteratively

Bypassability

• Which nodes should be bypassed?

• Average degree

• Relaxed edges

• To avoid the traps

• #shortcuts <= c·(InDegree (u)+OutDegree(u))

Radius

• Review

Dijkstra

Settle H nodes (H

L, a param on level L)

Monotony

Weight(u,v)+R(v)>=R(u)

Highway Construction

• Review Local and Highway

• 1 All highway edges of s X

• 2 highway edges

cross the neighborhood ?

• 3 Partial Shortest Path Tree √

PSPT

• To save time, PSPT could not be too large

• To keep the connectivity, it should be large

enough

• An Edge <u,v> belongs to highway network

iff there are nodes s and t, s.t.

<u,v> is on the canonical shortest path from

s to t && t !∈ N(s) && s! ∈N(t)

Abort Condition

• Abortion Condition : all nodes in the priority

queue are passive.

• A node p is passive, iff

PSPT Details

• Observations

1 Abortion condition => a(x)+r(x)<weight(x)

2 a(x)=weight(u), u1st node outside N(x)

3 u the grandparent of w, w1st node

outside N(s1)



4 w, weight(w)>b(w)=weight(s1)+R(s1)

PSPT Details

• 4->3->2->1

• 1) All nodes are active at the very beginning

• 2) when s1 is settled, set b(x):=weight(s1)+R(s1)

• 3) when w is settled(weight(w)>b(x)), set a(x):=

weight(u)

• 4) when p is settled(weight(x)>a(x)+r(x)), passive

•

5) nodes succeeding p are passive

PSPT Details

• It is ok, if |N(s1) ∩ N(p)|=0

• Monotony

Maverick

• An active endpoint of a long edge

active && weight(m)>f*(r(s0))

f, balance between preprocessing time and query time

• If all active nodes are maverick, search from

passive nodes is no longer continued.

• more highway edges

Edge Selection

• Edge<u,v> in neither R(s0) nor R(t0) are

Highway edges, where t0 is a leaf node of

PSPT and <u,v> is on path<s0,…,t0>.

Details

• Slack and Weight

Weight, distance from s0

Slack, ‘distance’ from the border of N(p)

• Backward Evaluation

• Edges start from nodes with slack<0 are highway

edges

•

Terminate if a node has a smaller slack already

Considerations

• DAG (Directed Acyclic Graph) vs. PSPT

partial shortest-path directed acyclic(no circle)

graph

edges in red ∈PsPT

edges in red&green ∈ DAG

• DAG vs. PSPT with Shadows

Considerations

• Turn Cost Model

• Abort Condition

Monotony X

r(s0)>b’(x)=weight(s1)+turncost(s1)+r(s1)

b(x)=max{r(s0),b’(x)}

• Slack

Query

• Bidirectional Dijkstra

s t

• Bidirectional A*

Query

• hierarchies

Query

Preprocessing vs. Query

• Routing type(Cost Function) 1 v 4(shorest

vs. fastest)

• We have to tune RCM(Road Cost Model)

and improve TCM(Turn Cost Model)

Different RCMs

edgeWeightForSearch/edgeWeightForUpgrade

Different TCMs

no turncost added to

edgeWeightForSearch

delay upgrading